﻿#pragma once

#include "utility.h"
#include "vector.h"
#include "stack.h"
#include "queue.h"
#include "tree_iterator.h"

namespace qyc
{
	template<class T>
	struct AVLTreeNode
	{
	private:
		typedef T data_type;
		typedef AVLTreeNode<data_type> self;
		typedef self* self_pointer;
	public:
		explicit AVLTreeNode(const data_type& data)
			: _data(data)
		{}
		explicit AVLTreeNode(data_type&& data = data_type())
			: _data(qyc::forward<data_type>(data))
		{}
		template<class... Args>
		AVLTreeNode(Args&&... args)
			: _data(args...)
		{}

		void swap(self& node)
		{
			qyc::swap(_data, node._data);
			qyc::swap(_bf, node._bf);
			qyc::swap(_pLeft, node._pLeft);
			qyc::swap(_pRight, node._pRight);
			qyc::swap(_pParent, node._pParent);
		}

		data_type _data = data_type();
		int _bf = 0;
		self_pointer _pLeft = nullptr;
		self_pointer _pRight = nullptr;
		self_pointer _pParent = nullptr;
	};

	template<class K, class T, class KeyOfValue, class Compare = less<K>>
	class AVLTree
	{
		typedef T data_type;
		typedef data_type& reference;
		typedef const data_type& const_reference;
		typedef data_type* pointer;
		typedef const data_type* const_pointer;

		typedef AVLTreeNode<data_type> Node;
		typedef Node* NodePtr;
		typedef AVLTree<K, data_type, KeyOfValue, Compare> self;
	public:
		typedef __tree_iterator<Node, K, T, KeyOfValue, Compare> iterator;
		typedef __tree_const_iterator<Node, K, T, KeyOfValue, Compare> const_iterator;
		typedef __reverse_iterator<iterator> reverse_iterator;
		typedef __reverse_iterator<const_iterator> const_reverse_iterator;

		AVLTree()
			: _pHead(new Node(data_type()))
		{}
		AVLTree(const self& des)
			: _pHead(new Node(data_type()))
			, _root(copy(des._root))
		{
			keep_HeadNode();
		}
		AVLTree(self&& des)
			: _pHead(new Node(data_type()))
		{
			swap(des);
		}
		template<class InputIterator>
		AVLTree(InputIterator first, InputIterator last)
			: _pHead(new Node(data_type()))
		{
			insert_equal_range(first, last);
		}
		AVLTree(std::initializer_list<data_type> _Ilist)
		{
			insert_equal_range(_Ilist.begin(), _Ilist.end());
		}
		self& operator=(const self& des)
		{
			if (&des != this)
			{
				destory(_root);
				_root = copy(des._root);
				keep_HeadNode();
			}
			return *this;
		}
		self& operator=(self&& des)
		{
			swap(des);
			return *this;
		}

		iterator begin()
		{
			return iterator(_pHead->_pLeft, _pHead);
		}
		iterator end()
		{
			return iterator(_pHead, _pHead);
		}
		const_iterator begin() const
		{
			return const_iterator(_pHead->_pLeft, _pHead);
		}
		const_iterator end() const
		{
			return const_iterator(_pHead, _pHead);
		}
		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}
		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}
		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(end());
		}
		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(begin());
		}

		pair<iterator, bool> insert(const data_type& data)
		{
			return _insert(new Node(data));
			//KeyOfValue kov = {};
			//Compare cmp = {};
			//NodePtr parent = nullptr;
			//NodePtr* ptr = &_root;
			//for (NodePtr cur = *ptr; cur != nullptr; cur = *ptr)
			//{
			//	if (cmp(kov(data), kov(cur->_data)))
			//	{
			//		parent = cur;
			//		ptr = &cur->_pLeft;
			//	}
			//	else if (cmp(kov(cur->_data), kov(data)))
			//	{
			//		parent = cur;
			//		ptr = &cur->_pRight;
			//	}
			//	else
			//		return make_pair(iterator(cur, _pHead), false);
			//}
			//*ptr = new Node(data, 0, parent);
			//_insert_keep_balance(*ptr, parent);
			//NodePtr cur = *ptr;
			//while (cur != _root)
			//{
			//	if (cur == parent->_pLeft)
			//		--parent->_bf;
			//	else
			//		++parent->_bf;

			//	if (parent->_bf == 0)
			//		break;
			//	else if (parent->_bf == 1 || parent->_bf == -1)
			//	{
			//		cur = parent;
			//		parent = cur->_pParent;
			//	}
			//	else	//parent->_bf == 2 || parent->_bf == -2
			//	{
			//		if (cur->_bf * parent->_bf > 0)
			//		{	//cur->bf 和 parent->_bf 同号时,只需一次单旋 
			//			if (parent->_bf > 0)
			//				rotate_left(parent);
			//			else
			//				rotate_right(parent);
			//		}
			//		else	//cur->bf 和 parent->_bf 异号时,需两次单旋
			//		{
			//			if (parent->_bf > 0)
			//				rotate_right_left(parent);
			//			else
			//				rotate_left_right(parent);
			//		}
			//		break;	//当旋转完成后,原根子树的高度降低,已平衡,无需再向上调整 
			//	}
			//}
			//keep_HeadNode();
			//return make_pair(iterator(*ptr, _pHead), true);
		}
		pair<iterator, bool> insert(data_type&& data)
		{
			return _insert(new Node(qyc::forward<data_type>(data)));
		}
		template<class... Args>
		pair<iterator, bool> emplace(Args&&... args)
		{
			return _insert(new Node(args...));
		}
		template<class InputIterator>
		void insert_range(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				insert(*first);
				++first;
			}
		}
		pair<iterator, bool> insert_equal(const data_type& data)
		{
			return _insert_equal(new Node(data));
			//KeyOfValue kov = {};
			//Compare cmp = {};
			//NodePtr parent = nullptr;
			//NodePtr* ptr = &_root;
			//for (NodePtr cur = *ptr; cur != nullptr; cur = *ptr)
			//{
			//	if (cmp(kov(data), kov(cur->_data)))
			//	{
			//		parent = cur;
			//		ptr = &cur->_pLeft;
			//	}
			//	else	//key相等放右边,不绝对(旋转后位置会改变)
			//	{
			//		parent = cur;
			//		ptr = &cur->_pRight;
			//	}
			//}
			//*ptr = new Node(data, 0, parent);
			//_insert_keep_balance(*ptr, parent);
			//keep_HeadNode();
			//return make_pair(iterator(*ptr, _pHead), true);
		}
		pair<iterator, bool> insert_equal(data_type&& data)
		{
			return _insert_equal(new Node(qyc::forward<data_type>(data)));
		}
		template<class... Args>
		pair<iterator, bool> emplace_equal(Args&&... args)
		{
			return _insert_equal(new Node(args...));
		}
		template<class InputIterator>
		void insert_equal_range(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				insert_equal(*first);
				++first;
			}
		}
		//bool erase(const K& key)
		//{
		//	KeyOfValue kov = {};
		//	Compare cmp = {};
		//	NodePtr parent = nullptr;
		//	NodePtr* ptr = &_root;
		//	for (NodePtr cur = *ptr; cur != nullptr; cur = *ptr)
		//	{
		//		if (cmp(key, kov(cur->_data)))
		//		{
		//			parent = cur;
		//			ptr = &cur->_pLeft;
		//		}
		//		else if (cmp(kov(cur->_data), key))
		//		{
		//			parent = cur;
		//			ptr = &cur->_pRight;
		//		}
		//		else
		//		{
		//			_erase(ptr);
		//			keep_HeadNode();
		//			return true;
		//		}
		//	}
		//	return false;
		//}
		bool erase(const K& key)
		{
			iterator result = find(key);
			if (result != end())
			{
				NodePtr cur = result._node;
				NodePtr parent = cur->_pParent;
				NodePtr* ptr = parent == nullptr ? &_root : (cur == parent->_pLeft ? &parent->_pLeft : &parent->_pRight);
				_erase(ptr);
				keep_HeadNode();
				return true;
			}
			else
				return false;
		}

		iterator find(const K& key)
		{
			KeyOfValue kov = KeyOfValue();
			Compare cmp = Compare();
			for (NodePtr cur = _root; cur != nullptr; )
			{
				if (cmp(key, kov(cur->_data)))
					cur = cur->_pLeft;
				else if (cmp(kov(cur->_data), key))
					cur = cur->_pRight;
				else
				{
					iterator prev(cur, _pHead);
					for (iterator it(cur, _pHead); it != end() && !cmp(kov(*it), key) && !cmp(key, kov(*it)); --it)
						prev = it;
					return prev;
				}
			}
			return end();
		}
		const_iterator find(const K& key) const
		{
			KeyOfValue kov = KeyOfValue();
			Compare cmp = Compare();
			for (NodePtr cur = _root; cur != nullptr; )
			{
				if (cmp(key, kov(cur->_data)))
					cur = cur->_pLeft;
				else if (cmp(kov(cur->_data), key))
					cur = cur->_pRight;
				else
				{
					const_iterator prev(cur, _pHead);
					for (const_iterator it(cur, _pHead); it != end() && !cmp(kov(*it), key) && !cmp(key, kov(*it)); --it)
						prev = it;
					return prev;
				}
			}
			return end();
		}

		size_t hight() const
		{
			return _hight(_root);
		}
		bool balance() const
		{
			return _balance(_root);
		}
		bool empty() const
		{
			return _root == nullptr;
		}
		size_t size() const
		{
			return inorder().size();
			//queue<NodePtr> q;
			//size_t count = 0;
			//if (_root != nullptr)
			//	q.push(_root);
			//while (!q.empty())
			//{
			//	size_t levelSize = q.size();
			//	count += levelSize;
			//	for (size_t i = 0; i < levelSize; ++i)
			//	{
			//		NodePtr cur = q.top();
			//		q.pop();
			//		if (cur->_pLeft != nullptr)
			//			q.push(cur->_pLeft);
			//		if (cur->_pRight != nullptr)
			//			q.push(cur->_pRight);
			//	}
			//}
			//return count;
		}
		void clear()
		{
			destory(_root);
			_pHead->_pLeft = nullptr;
			_pHead->_pRight = nullptr;
		}
		void swap(self& des)
		{
			qyc::swap(_root, des._root);
			qyc::swap(_pHead, des._pHead);
		}
		bool operator==(const self& des) const
		{
			return compare(_root, des._root);
		}
		bool operator!=(const self& des) const
		{
			return !compare(_root, des._root);
		}
		vector<vector<data_type>> levelorder() const
		{
			queue<NodePtr> q;
			vector<vector<data_type>> ret;
			if (_root != nullptr)
				q.push(_root);
			while (!q.empty())
			{
				vector<data_type> tmp;
				size_t levelSize = q.size();
				for (size_t i = 0; i < levelSize; ++i)
				{
					NodePtr cur = q.front();
					tmp.push_back(cur->_data);
					q.pop();
					if (cur->_pLeft != nullptr)
						q.push(cur->_pLeft);
					if (cur->_pRight != nullptr)
						q.push(cur->_pRight);
				}
				ret.push_back(tmp);
			}
			return ret;
		}
		vector<data_type> preorder() const
		{
			vector<data_type> ret;
			stack<NodePtr> st;
			NodePtr cur = _root;
			while (cur || !st.empty())
			{
				while (cur)
				{
					st.push(cur);
					ret.push_back(cur->_data);
					cur = cur->_pLeft;
				}
				NodePtr top = st.top();
				st.pop();
				if (top->_pRight)
					cur = top->_pRight;
			}
			return ret;
		}
		vector<data_type> inorder() const
		{
			vector<data_type> ret;
			stack<NodePtr> st;
			NodePtr cur = _root;
			while (cur || !st.empty())
			{
				while (cur)
				{
					st.push(cur);
					cur = cur->_pLeft;
				}
				NodePtr top = st.top();
				st.pop();
				ret.push_back(top->_data);
				if (top->_pRight)
					cur = top->_pRight;
			}
			return ret;
		}
		vector<data_type> postorder() const
		{
			vector<data_type> ret;
			stack<NodePtr> st;
			NodePtr prev = nullptr;
			NodePtr cur = _root;
			while (cur || !st.empty())
			{
				while (cur)
				{
					st.push(cur);
					cur = cur->_pLeft;
				}
				NodePtr top = st.top();
				if (top->_pRight == nullptr || prev == top->_pRight)
				{
					prev = top;
					ret.push_back(top->_data);
					st.pop();
				}
				else
					cur = top->_pRight;
			}
			return ret;
		}
		~AVLTree()
		{
			destory(_root);
			delete _pHead;
			_pHead = nullptr;
		}
	private:
		const NodePtr get_minNode()
		{
			NodePtr cur = _root;
			while (cur && cur->_pLeft != nullptr)
				cur = cur->_pLeft;
			return cur;
		}
		const NodePtr get_maxNode()
		{
			NodePtr cur = _root;
			while (cur && cur->_pRight != nullptr)
				cur = cur->_pRight;
			return cur;
		}
		void keep_HeadNode()
		{
			_pHead->_pLeft = get_minNode();
			_pHead->_pRight = get_maxNode();
		}

		//新节点插入较高右子树的右侧	右右:左单旋
		NodePtr rotate_left(NodePtr root)
		{
			NodePtr cur = root->_pRight;
			NodePtr parent = root->_pParent;
			NodePtr left = cur->_pLeft;

			if (root != _root)
			{
				if (parent->_pLeft == root)
					parent->_pLeft = cur;
				else
					parent->_pRight = cur;
			}
			else
				_root = cur;
			cur->_pParent = parent;

			cur->_pLeft = root;
			root->_pParent = cur;
			
			root->_pRight = left;
			if (left)
				left->_pParent = root;

			root->_bf = cur->_bf = 0;
			return cur;
		}
		//新节点插入较高左子树的左侧	左左:右单旋
		NodePtr rotate_right(NodePtr root)
		{
			NodePtr cur = root->_pLeft;
			NodePtr parent = root->_pParent;
			NodePtr right = cur->_pRight;

			if (root != _root)
			{
				if (parent->_pLeft == root)
					parent->_pLeft = cur;
				else
					parent->_pRight = cur;
			}
			else
				_root = cur;
			cur->_pParent = parent;

			root->_pParent = cur;
			cur->_pRight = root;

			root->_pLeft = right;
			if (right)
				right->_pParent = root;

			root->_bf = cur->_bf = 0;
			return cur;
		}
		//新节点插入较高左子树的右侧	左右:先左单旋再右单旋
		NodePtr rotate_left_right(NodePtr root)
		{
			NodePtr cur = root->_pLeft;
			int bf = cur->_pRight->_bf;
			rotate_left(cur);
			NodePtr ret = rotate_right(root);
			if (bf == 1)
			{	//当插入到较高左子树右子树的右侧时
				root->_bf = 0;
				cur->_bf = -1;
			}
			else if (bf == -1)
			{	//当插入到较高左子树右子树的左侧时
				root->_bf = 1;
				cur->_bf = 0;
			}
			else if (bf == 0)
			{	//当插入节点为较高左子树右子树本身
				root->_bf = 0;
				cur->_bf = 0;
			}
			return ret;
		}
		//新节点插入较高右子树的左侧	右左:先右单旋再左单旋
		NodePtr rotate_right_left(NodePtr root)
		{
			NodePtr cur = root->_pRight;
			int bf = cur->_pLeft->_bf;
			rotate_right(cur);
			NodePtr ret = rotate_left(root);
			if (bf == 1)
			{	//当插入到较高右子树左子树的右侧时
				cur->_bf = 0;
				root->_bf = -1;
			}
			else if (bf == -1)
			{	//当插入到较高右子树左子树的左侧时
				root->_bf = 0;
				cur->_bf = 1;
			}
			else if (bf == 0)
			{	//当插入节点为较高右子树左子树本身
				root->_bf = 0;
				cur->_bf = 0;
			}
			return ret;
		}
		pair<iterator, bool> _insert(NodePtr node)
		{
			KeyOfValue kov = KeyOfValue();
			pair<NodePtr*, NodePtr> ret = _insert_find_position(kov(node->_data));
			if (*(ret.first) != nullptr)
			{
				delete node;
				return pair<iterator, bool>(iterator(*(ret.first), _pHead), false);
			}
			else
			{
				node->_pParent = ret.second;
				*(ret.first) = node;
			}
			_insert_keep_balance(node, ret.second);
			keep_HeadNode();
			return pair<iterator, bool>(iterator(node, _pHead), true);
		}
		pair<iterator, bool> _insert_equal(NodePtr node)
		{
			KeyOfValue kov = KeyOfValue();
			pair<NodePtr*, NodePtr> ret = _insert_equal_find_position(kov(node->_data));
			node->_pParent = ret.second;
			*(ret.first) = node;
			_insert_keep_balance(node, ret.second);
			keep_HeadNode();
			return pair<iterator, bool>(iterator(node, _pHead), true);
		}
		pair<NodePtr*, NodePtr> _insert_find_position(const K& key)
		{
			KeyOfValue kov = KeyOfValue();
			Compare cmp = Compare();
			NodePtr parent = nullptr;
			NodePtr* ptr = &_root;
			for (NodePtr cur = *ptr; cur != nullptr; cur = *ptr)
			{
				if (cmp(key, kov(cur->_data)))
				{
					parent = cur;
					ptr = &cur->_pLeft;
				}
				else if (cmp(kov(cur->_data), key))
				{
					parent = cur;
					ptr = &cur->_pRight;
				}
				else
					break;
			}
			return pair<NodePtr*, NodePtr>(ptr, parent);
		}
		pair<NodePtr*, NodePtr> _insert_equal_find_position(const K& key)
		{
			KeyOfValue kov = KeyOfValue();
			Compare cmp = Compare();
			NodePtr parent = nullptr;
			NodePtr* ptr = &_root;
			for (NodePtr cur = *ptr; cur != nullptr; cur = *ptr)
			{
				if (cmp(key, kov(cur->_data)))
				{
					parent = cur;
					ptr = &cur->_pLeft;
				}
				else	//key相等放右边,不绝对(旋转后位置会改变)
				{
					parent = cur;
					ptr = &cur->_pRight;
				}
			}
			return pair<NodePtr*, NodePtr>(ptr, parent);
		}
		void _insert_keep_balance(NodePtr cur, NodePtr parent)
		{
			while (cur != _root)
			{
				if (cur == parent->_pLeft)
					--parent->_bf;
				else
					++parent->_bf;

				if (parent->_bf == 0)
					break;
				else if (parent->_bf == 1 || parent->_bf == -1)
				{
					cur = parent;
					parent = cur->_pParent;
				}
				else	//parent->_bf == 2 || parent->_bf == -2
				{
					if (cur->_bf * parent->_bf > 0)
					{	//cur->bf 和 parent->_bf 同号时,只需一次单旋 
						if (parent->_bf > 0)
							rotate_left(parent);
						else
							rotate_right(parent);
					}
					else	//cur->bf 和 parent->_bf 异号时,需两次单旋
					{
						if (parent->_bf > 0)
							rotate_right_left(parent);
						else
							rotate_left_right(parent);
					}
					break;	//当旋转完成后,原根子树的高度降低,已平衡,无需再向上调整 
				}
			}
		}
		void _node_swap_position(NodePtr left, NodePtr right)
		{
			qyc::swap(left->_pParent, right->_pParent);
			bool flagL = false, flagR = false;
			if (right != _root)
			{
				flagR = true;
				if (left->_pParent->_pLeft == right)
					left->_pParent->_pLeft = left;
				else
					left->_pParent->_pRight = left;
			}
			if (left != _root)
			{
				flagL = true;
				if (right->_pParent->_pLeft == left)
					right->_pParent->_pLeft = right;
				else
					right->_pParent->_pRight = right;
			}
			if (flagL == false)
				_root = right;
			if (flagR = false)
				_root = left;

			qyc::swap(left->_pLeft, right->_pLeft);
			if (left->_pLeft != nullptr)
				left->_pLeft->_pParent = left;
			if (right->_pLeft != nullptr)
				right->_pLeft->_pParent = right;

			qyc::swap(left->_pRight, right->_pRight);
			if (left->_pRight != nullptr)
				left->_pRight->_pParent = left;
			if (right->_pRight != nullptr)
				right->_pRight->_pParent = right;

			qyc::swap(left->_bf, right->_bf);
		}
		void _erase(NodePtr* ptr)
		{
			NodePtr cur = *ptr;
			if (cur->_pLeft != nullptr && cur->_pRight != nullptr)
			{
				NodePtr rightMin = cur->_pRight;
				ptr = &cur->_pRight;
				while (rightMin->_pLeft != nullptr)
				{
					ptr = &rightMin->_pLeft;
					rightMin = *ptr;
				}
				//cur->_data = qyc::move(rightMin->_data);
				_node_swap_position(cur, rightMin);
			}
			NodePtr delcur = cur;
			NodePtr delparent = cur->_pParent;

			NodePtr parent = cur->_pParent;
			while (cur != _root)
			{
				if (cur == parent->_pLeft)
					++parent->_bf;
				else if (cur == parent->_pRight)
					--parent->_bf;

				if (parent->_bf == 0)
				{	//从-1/1变为0时,高度变化,须向上更新
					cur = parent;
					parent = parent->_pParent;
				}
				else if (parent->_bf == 1 || parent->_bf == -1)
					break;		//从0变为-1/1时,高度不变
				else if (parent->_bf == 2 || parent->_bf == -2)
				{
					if (parent->_bf == 2)
					{
						if (parent->_pRight->_bf == 1)
							parent = rotate_left(parent);
						else if (parent->_pRight->_bf == -1)
							parent = rotate_right_left(parent);
						else if (parent->_pRight->_bf == 0)
						{	//该情况调整后,高度不变,无需向上更新
							parent = rotate_left(parent);
							parent->_bf = -1;
							parent->_pLeft->_bf = 1;
							break;
						}
					}
					else if (parent->_bf == -2)
					{
						if (parent->_pLeft->_bf == -1)
							parent = rotate_right(parent);
						else if (parent->_pLeft->_bf == 1)
							parent = rotate_left_right(parent);
						else if (parent->_pLeft->_bf == 0)
						{	//该情况调整后,高度不变,无需向上更新
							parent = rotate_right(parent);
							parent->_bf = 1;
							parent->_pRight->_bf = -1;
							break;
						}
					}
					cur = parent;
					parent = parent->_pParent;
				}
			}
			//先调整再删除,保证调整时cur不为nullptr
			NodePtr noempty = delcur->_pLeft == nullptr ? delcur->_pRight : delcur->_pLeft;
			if (noempty)
				noempty->_pParent = delparent;
			delete delcur;
			*ptr = noempty;
		}
		NodePtr copy(NodePtr root)
		{
			if (root == nullptr)
				return nullptr;
			NodePtr ret = new Node(root->_data);
			ret->_bf = root->_bf;
			ret->_pLeft = copy(root->_pLeft);
			if (ret->_pLeft)
				ret->_pLeft->_pParent = ret;
			ret->_pRight = copy(root->_pRight);
			if (ret->_pRight)
				ret->_pRight->_pParent = ret;
			return ret;
		}

		size_t _hight(NodePtr root) const
		{
			if (root == nullptr)
				return 0;
			size_t left = _hight(root->_pLeft);
			size_t right = _hight(root->_pRight);
			return 1 + (left > right ? left : right);
		}
		bool _balance(NodePtr root) const
		{
			if (root == nullptr)
				return true;
			if (root->_bf != _hight(root->_pRight) - _hight(root->_pLeft) || (root->_bf < -1 || root->_bf > 1))
				return false;
			else
				return (_balance(root->_pLeft) && _balance(root->_pRight));
		}
		bool compare(NodePtr des, NodePtr src) const
		{
			if (des == nullptr && src == nullptr)
				return true;
			if (des == nullptr || src == nullptr)
				return false;
			return (des->_data == src->_data) && (des->_bf == src->_bf) \
					&& compare(des->_pLeft, src->_pLeft) && compare(des->_pRight, src->_pRight);
		}
		void destory(NodePtr& root)
		{
			if (root == nullptr)
				return;
			destory(root->_pLeft);
			destory(root->_pRight);
			delete root;
			root = nullptr;
		}

		NodePtr _pHead = nullptr;
		NodePtr _root = nullptr;
	};
}